package com.sheng.leetcode.year2023.swordfingerofferspecial.day02;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/03/02
 * <p>
 * 剑指 Offer II 004. 只出现一次的数字<p>
 * <p>
 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [2,2,3,2]<p>
 * 输出：3<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [0,1,0,1,0,1,100]<p>
 * 输出：100<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 3 * 10^4<p>
 * -2^31 <= nums[i] <= 2^31 - 1<p>
 * nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次<p>
 * <p>
 * 进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？<p>
 * <p>
 * 注意：本题与主站 137 题相同：<a href="https://leetcode-cn.com/problems/single-number-ii/">主站 137</a><p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/WGki4K">剑指 Offer II 004. 只出现一次的数字</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword004 {

    @Test
    public void test01() {
        int[] nums = {2, 2, 3, 2};
//        int[] nums = {0, 1, 0, 1, 0, 1, 100};
        System.out.println(new Solution().singleNumber(nums));
    }
}

//class Solution {
//    public int singleNumber(int[] nums) {
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int num : nums) {
//            map.put(num, map.getOrDefault(num, 0) + 1);
//        }
//        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
//            if (entry.getValue() == 1) {
//                return entry.getKey();
//            }
//        }
//        return -1;
//    }
//}

//哈希表解法的空间复杂度是O(n) 的，而题目的【进阶】部分提到应当使用常数空间来做。
//其中一个比较容易想到的做法，是利用int 类型固定为32 位。
//使用一个长度为32 的数组cnt[] 记录下所有数值的每一位共出现了多少次1，再对cnt[] 数组的每一位进行mod3 操作，重新拼凑出只出现一次的数值。
//举个 🌰，考虑样例 [1,1,1,3]，1 和 3对应的二进制表示分别是 00..001 和 00..011，存入cnt[] 数组后得到 [0,0,...,0,1,4]。进行
//mod3 操作后得到 [0,0,...,0,1,1]，再转为十进制数字即可得「只出现一次」的答案3。
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/WGki4K/solution/by-ac_oier-npwu/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
    public int singleNumber(int[] nums) {
        int[] cnt = new int[32];
        for (int x : nums) {
            for (int i = 0; i < 32; i++) {
                if (((x >> i) & 1) == 1) {
                    cnt[i]++;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if ((cnt[i] % 3 & 1) == 1) {
                ans += (1 << i);
            }
        }
        return ans;
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/WGki4K/solution/by-ac_oier-npwu/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
